class Solution:
    def twoSum(self, nums, target):
        # O(n^2)
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return i, j
        return -1, -1

    def binary_sort(self, li, left, right, val):
        while left < right:
            mid = (left + right) // 2
            if li[mid][0] == val:
                return mid
            if li[mid][0] < val:
                right = mid - 1
            else:
                left = mid + 1
        else:
            return None

    def towSum_2(self, nums, target):
        # O(nlogn)
        new_nums = [[num, i] for i, num in enumerate(nums)]
        new_nums.sort(key=lambda x: x[0])

        n = len(new_nums)
        for i in range(n):
            a = new_nums[i][0]
            b = target - a
            if b >= a:
                j = self.binary_sort(new_nums, i+1, n-1, b)
            else:
                j = self.binary_sort(new_nums, 0, i-1, b)
            if j:
                break
        return sorted([new_nums[i][1], new_nums[j][1]])

nums = [3, 2, 4]
sl = Solution()
print(sl.towSum_2(nums, 6))
